// ShellSort.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>

void PrintArray(int inArray[], int length) {
    for (int i = 0; i < length; i++) {
        printf("%d ", inArray[i]);
    }
    printf("\n");
}

void ShellSort(int inArray[], int length, int step) {
    //对根据步长分组的各个数组进行插入排序
    for (int i = 0; i < length; i ++) {
        //挑选 当前元素 出根据步长分组的数组
        for (int j = i; j < length; j += step) {
            //进行 插入排序
            for (int k = i; k < j; k += step) {
                int tempJ = inArray[j];
                if (inArray[j] < inArray[k]) {
                    for (int l = j; l > k; l -= step) {
                        inArray[l] = inArray[l - step];
                    }
                    inArray[k] = tempJ;
                }
            }
        }
    }
    PrintArray(inArray, length);
}

int main()
{
    int inArray[] = { 4, 3, 5, 1, 9, 6, 7, 8, 3, 2 };
    int step[] = { 5, 3, 1 };

    printf("希尔排序:\n");
    PrintArray(inArray, 10);
    for (int i = 0; i < 3; i ++) {
        ShellSort(inArray, 10, step[i]);
    }
}